#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline int phi(int n){  
    int r,a;
    r = a = n;
    for(int i=2;i*i<=a;++i){
        if(a%i) continue;
        r = r / i * (i-1);  
        while(!(a%i)) a /= i;
    }  
    if(a>1) r = r / a * (a-1);
    return r;  
}

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)){
    	x = (x<<3)+(x<<1)+c-'0';
    	c = getchar();
    }
}

inline int power(int a,int t,int p){
    int r = 1;
    while(t){
        if(t&1) r = (ll)r*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return r;
}

int tower(int c,int p){ 
    if(p==1) return 0;
    int t = phi(p);
    return power(c,tower(c,t)+t,p);
}

void sc(int x){
    if(x > 9) sc(x / 10);
    putchar(x%10+'0');
}

void optimized(){
    int m;
    read(m);
    sc(tower(2,m));
    putchar('\n');
}

int main(){
    int T;
    read(T);
    while(T--)
        optimized(); 
    return 0;
}

